public class BSTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root;

    /** 查找val
     *最好情况：O(logN)
     * 最坏情况：O(N)
     * @param val
     * @return
     */
    public boolean search(int val){
        TreeNode cur=root;
        while(cur!=null){
            if(val>cur.val){
                cur=cur.right;
            }else if(val<cur.val){
                cur=cur.left;
            }else{
                return true;
            }
        }
        return false;
    }

    /** 插入val
     *
     * @param val
     */
    public void insert(int val){
        TreeNode node=new TreeNode(val);
        if(root==null){
            root=node;
            return;
        }
        TreeNode cur=root;
        TreeNode parent=null;
        while(cur!=null){
            if(val>cur.val){
                parent=cur;
                cur=cur.right;
            }else if(val<cur.val){
                parent=cur;
                cur=cur.left;
            }else{
                return;
            }
        }
        if(val>parent.val){
            parent.right=node;
        }else{
            parent.left=node;
        }
    }
}
